package leetcode.hash;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class A781 {

    public int numRabbits(int[] answers) {
//每次问的是不同的个体，对于回答一样且大于0的，他们的颜色可能相同，可能不同，相同的话最好，这样他们处于一个集合，数量最少
        //如果回答是0，他自己属于一个集合
        //假设同一个集合(同颜色为一个集合)有n只兔子，如果这个集合的兔子都回答，那么他们回答n-1共n次，当然不一定每只兔子都回答，但是我们尽量把出现回答一样的认定为一个集合，使得集合数量尽可能少
        // 也对于数组中出现的数字x，如果出现的次数<=x+1，那么我们认为他们属于一个集合，超出了则认为在另一个集合
        //所以x出现次数/(x+1)向上取整是最少的集合数量，再乘以x+1即可
        Integer res=0;
      //  Set<Integer> set=new HashSet<>();
        //集合n个人，回答t(n-1)最多n次
        Map<Integer,Integer> map=new HashMap<>();
        for (int answer : answers) {
            if(answer==0)res+=1;
        else map.put(answer,map.getOrDefault(answer,0)+1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int key=entry.getKey();//回答      1
int value=entry.getValue();//回答的数量     2
int count=key+1;//集合n个人     2
            //计算value/count向上取整 即(a+b-1)/b,如果a/b刚好整除，不影响结果，如果超出了(1,b-1)那么加上b-1会使结果大于1
        int nums=(value+count-1)/count;//集合的数量
         res+=nums*count;

        }
        return res;
    }
}
